package com.bascker.algorithm.practice.greed;

import java.util.Objects;

/**
 * 跳跃游戏 II:
 *   给定一个非负整数数组，你最初位于数组的第一个位置, 数组中的每个元素代表你在该位置可以跳跃的最大长度。
 *   目标是使用最少的跳跃次数到达数组的最后一个位置.
 *
 * Note: 假设总是可以到达数组的最后一个位置
 *
 * @author bascker
 * @apiNote from leetcode T45
 * @implNote https://gitee.com/bascker/algorithm/wikis/2%E3%80%81%E8%B7%B3%E8%B7%83%E6%B8%B8%E6%88%8FII?sort_id=2992763
 */
public class JumpII {

    public int jump(int[] nums) {
        if (Objects.isNull(nums) || nums.length == 0) {
            return 0;
        }

        int n = nums.length;
        // 跟踪下一次跳跃的位置
        int location = 0;
        // 跟踪当前位置跳跃时可跳位置的最远处
        int end = 0;
        int step = 0;

        // i 表示当前位置：最后一个位置无需遍历
        for (int i = 0; i < n - 1; ++i) {
            location = Math.max(location, i + nums[i]);

            // 到达跳跃位置时
            if (i == end) {
                end = location;
                step ++;
            }
        }

        return step;
    }

}
